package shu;

import utils.Utils;

public class _05要排序的子数组 {
    /**
     * 给定一个无序数组arr，求出需要排序的最短子数组长度
     * 要求：
     * O (N)
     * 如输入：arr={2,3,7,5,4,6}，返回4，因为只有{7,5,4,6}需要排序
     * 如输入：arr={1,5,3,4,2,6,7}，返回4，因为只有{5,3,4,2}需要排序
     * 从左往右数，第一个最大的后面有几个比他小的
     * 从右往左数，第一个最小的前面有几个比他大的
     */
    private int[] findSegment(int[] a, int n) {
        //拓展右端点：更新历史最高，只要右侧出现比历史最高低的，就应该将右边界扩展到此处（从左往右）
        int p1 = -1;
        int p2 = -1;
        int max = a[0];
        int min = a[n-1];
        for (int i = 0 ; i < n;i++){
            if (a[i] > max){
                max = a[i];
            }
            //只要低于历史高峰，就要扩展需排序区间的右端点
            if (a[i] < max){
                p2 = i;
            }
        }
        //找左端点：更新历史最低，只要左侧出现比历史最低高的，就应该将左边界扩展到此处（从右往左）
        for (int i = n-1 ;i >= 0 ;i--){
            if (a[i] < min){
                min = a[i];
            }
            if (a[i] > min){
                p1 = i;
            }

        }
        if (p1 == -1){
            return new int[]{0,0};
        }
        return new int[]{p1,p2};
    }


    public static void main(String[] args) {
        _05要排序的子数组 obj = new _05要排序的子数组();
        int[] A = {1, 4, 6, 5, 9, 10};
        int[] res = obj.findSegment(A, 6);
        Utils.print(res);

        A = new int[]{1, 2, 3, 4, 5, 6};
        res = obj.findSegment(A, A.length);
        Utils.print(res);

        A = new int[]{1, 5, 3, 4, 2, 6, 7};
        res = obj.findSegment(A, A.length);
        Utils.print(res);

        A = new int[]{2, 3, 7, 5, 4, 6};
        res = obj.findSegment(A, A.length);
        Utils.print(res);
        A = new int[]{3, 2, 5, 6, 7, 8};
        res = obj.findSegment(A, A.length);
        Utils.print(res);

        A = new int[]{2, 8, 7, 10, 9};
        res = obj.findSegment(A, A.length);
        Utils.print(res);

        A = new int[]{2, 3, 7, 4, 1, 5, 6};
        res = obj.findSegment(A, A.length);
        Utils.print(res);

        A = new int[]{2,3,7,4,3,5,6,};
        res = obj.findSegment(A, A.length);
        Utils.print(res);
    }


}
